package hwThree4;

import java.util.HashSet;

public class PerfectHashFunction {
    public static void main(String[] args) {
        // 字母序号映射
        int[] keys = {19, 5, 1, 18, 3, 8, 24, 13, 16, 12}; // 对应字母 S E A R C H X M P L

        int minM = 0; // 最小的 M
        int bestA = 0; // 对应的 A

        // 从 M = 10 开始尝试
        for (int M = 10; ; M++) {
            boolean found = false;

            // 遍历所有可能的 a 值
            for (int a = 1; a < M; a++) {
                HashSet<Integer> hashSet = new HashSet<>();
                boolean collision = false;

                // 计算每个键的散列值
                for (int key : keys) {
                    int hash = (a * key) % M;
                    if (hashSet.contains(hash)) { // 检查冲突
                        collision = true;
                        break;
                    }
                    hashSet.add(hash);
                }

                // 如果没有冲突，找到完美散列函数
                if (!collision) {
                    minM = M;
                    bestA = a;
                    found = true;
                    break;
                }
            }

            // 如果找到合适的 M 和 a，退出循环
            if (found) break;
        }

        // 输出结果
        System.out.println("最小的 M: " + minM);
        System.out.println("对应的 A: " + bestA);
        System.out.println("散列值:");
        for (int key : keys) {
            int hash = (bestA * key) % minM;
            System.out.println("Key " + key + " -> Index " + hash);
        }
    }
}